package bintree.leetcode;

//662. 二叉树最大宽度

import java.util.Deque;
import java.util.LinkedList;

public class Num662_widthOfBinaryTree {
    public int widthOfBinaryTree(TreeNode root) {
        if(root==null){
            return 0;
        }
        int maxWidth=0;
        Deque<NodeWithNum> queue=new LinkedList<>();
        queue.offer(new NodeWithNum(root,1));
        while (!queue.isEmpty()){
            int levelWidth=0;
            int L=0;
            int R=0;
            int size= queue.size();
            for (int i = 0; i < size; i++) {
                NodeWithNum cur=queue.poll();
                if(i==0){
                    L=cur.num;
                }
                if(i==size-1){
                    R=cur.num;
                }
                if(cur.node.left!=null){
                    queue.offer(new NodeWithNum(cur.node.left,cur.num*2));
                }
                if(cur.node.right!=null){
                    queue.offer(new NodeWithNum(cur.node.right,cur.num*2+1));
                }
            }
            levelWidth=R-L+1;
            maxWidth=Math.max(levelWidth,maxWidth);
        }
        return maxWidth;
    }
    private class NodeWithNum{
        TreeNode node;
        int num;

        public NodeWithNum(TreeNode node, int num) {
            this.node = node;
            this.num = num;
        }
    }
}
